#pragma once 
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;


template <class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
};

template <class K, class V>
class HashTable {
    public:
        HashTable() : _table(11), _n(0) {}
        typedef HashTable<K, V> Node;
        bool Insert(const pair<K, V>& kv) {
            Node* pos = Find(kv.first);
            if(pos) {
                return false;
            }
            // 刚刚超过了负载因子
            if(_n == _table.size()) {
                vector<Node*> newTable(_table.size() * 2);
                for(size_t i = 0; i < _table.size(); i++) {
                    Node* cur = _table[i];
                    while(cur) // 遍历原来哈希桶里面的节点
                    {
                        Node* next = cur->_next;
                        size_t hashi = cur->_kv.first % newTable.size();
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    _table[i] = nullptr; // 置空
                }
                _table.swap(newTable); // 交换
            }
            // 开始插入键值对
            size_t hashi = kv.first % _table.size();
            // 也是头插
            Node* newnode = new Node(kv);
            newnode->_next = _table[hashi];
            _table[hashi] = newnode;
            _n++;
            return true;
        }
        HashNode<K, V>* Find(const K& key) {
            size_t hashi = key % _table.size();
            HashNode<K, V>* cur = _table[hashi];
            while(cur) {
                if(cur->_kv.first == key) {
                    return cur;
                }
                cur = cur->_next;
            }
            return nullptr;
        }
        bool Erase(const K& key) {
            size_t hashi = key % _table.size();
            Node* prev = nullptr;
            Node* cur = _table[hashi];
            while(cur) {
                if(cur->_kv.first == key) {
                    if(prev == nullptr) // 头节点
                    {
                        _table[hashi] = cur->_next;
                    }else // 在中间
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    _n--;
                    return true;
                }else {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }
    private:
        vector<Node*> _table;
        size_t _n;
};